/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhong
 *
 */
public class LoudandRich {
	class Node {
		int quiet;
		int index;
		boolean visited = false;
		List<Node> r = new ArrayList<>();

		public Node(int q, int i) {
			this.quiet = q;
			this.index = i;
		}
	}

	public int[] loudAndRich(int[][] richer, int[] quiet) {
		int n = quiet.length;
		Node[] nodes = new Node[n];
		for (int i = 0; i < quiet.length; i++) {
			nodes[i] = new Node(quiet[i], i);
		}
		for (int[] i : richer) {
			nodes[i[1]].r.add(nodes[i[0]]);
		}
		int[] res = new int[n];
		for (int i = 0; i < res.length; i++) {
			BFS(nodes[i]);
			res[i] = nodes[i].index;
			System.out.println(res[i]);
		}
		return res;
	}

	/***
	 * 
	 * @param node
	 * @return 最小quiet的Node的编号
	 */
	private void BFS(Node node) {
		if (node.visited) {
			return;
		}
		node.visited = true;
		for (Node neib : node.r) {
			BFS(neib);
			if (neib.quiet < node.quiet) {
				node.quiet = neib.quiet;
				node.index = neib.index;
			}
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] richer = { { 1, 0 }, { 2, 1 }, { 3, 1 }, { 3, 7 }, { 4, 3 }, { 5, 3 }, { 6, 3 } };
		int[] quiet = { 3, 2, 5, 4, 6, 1, 7, 0 };
		System.out.println(new LoudandRich().loudAndRich(richer, quiet));
	}

}
